1. Field of the Invention
Embodiments of the present invention generally relate to 3-D object recognition and, in particular, to a method and apparatus for 3-D object recognition using indexing and verification methods.
2. Description of the Related Art
Object recognition, such as 3-D object recognition, involves the solution of several complicated problems. For example, there is (1) the unknown pose between the scene feature (e.g., several related points of a scene object in 3-D space) and the model, (2) the scene feature-model discrepancy due to occlusions and clutter in a given scene, and (3) the computational cost of comparing each individual model from a model database to match against the inputted scene feature. Alignment-based verification techniques have been used to address the first two problems. However, existing alignment-based techniques apply sequential RANSAC-based techniques to each individual model from the database and hence, do not address the computational issues related to the third problem when mapping to a large model database.
Stated another way, where there is a large model database and an inputted scene feature having several points, a determination must be made as to which model corresponds to this scene feature or set of scene features. Because of the limitation of sensors, the scene feature can be noisy and particularly occluded as compared with the model database. Therefore, indexing of the scene feature obtained from the scene for 3-D recognition and matching the model must be performed very quickly. For example, there may be between about 100 to 200 models in a given database. Each model has several hundred model features associated therewith. Traditionally, there has to be a comparison of the scene features with the model features in the model database sequentially (e.g., one-by-one). This is very time consuming, computationally extensive and costly.
Geometric hashing and its variants perform object recognition using high dimensional representations that combine (quasi-)invariant coordinate representations with geometric coordinate hashing to prune a model database while employing geometric constraints. However, the time and space complexity of creating geometric cache tables is polynomial in the number of feature points associated with each model. Furthermore, because the (quasi-)invariant coordinate representations are relatively low-dimensional (e.g., typically two or three), the hash table can become crowded even with small model databases and the runtime complexity can deteriorate to a linear complexity that again does not scale with the size of the database.
Thus, there is a need in the art for a joint feature-based model indexing and geometric constraint based alignment pipeline for efficient and accurate recognition of objects and especially 3-D objects. Furthermore, there is a need for recognition techniques used in recognizing 3-D objects from a large model database of 3-D range images.